//给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,2]
//输出：
//[[1,1,2],
// [1,2,1],
// [2,1,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 8 
// -10 <= nums[i] <= 10 
// 
// Related Topics 数组 回溯 👍 1057 👎 0

package leetcode.editor.cn;

import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution47 {
    List<List<Integer>> result = new ArrayList<>();
    Deque<Integer> path = new LinkedList<>();
    boolean[] used = null;//用数组去重需要排序
//    boolean[] shuCengUsed;  用一个used数组即可实现树枝或者树层去重，一般选择树层，效果高
    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
//        shuCengUsed = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums);
        return result;
    }

    public void backTracking(int[] nums){
        if(path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(used[i]) continue; //确保原始使用一次
            if(i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue; //树层去重
//            if(i > 0 && nums[i] == nums[i-1] && used[i-1]) continue; //树枝去重
            used[i] = true;
    //          huCengUsed[i] = true;
            path.add(nums[i]);
            backTracking(nums);
            used[i] = false;
//            shuCengUsed[i] = false;
            path.removeLast();
        }
    }


}
//leetcode submit region end(Prohibit modification and deletion)
